import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.lang.reflect.Array;
import java.util.*;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-03-08
 * Time:11:32
 */

/**
 * 2055. 蜡烛之间的盘子
 * 思路:前缀和
 * 1.左边端点的右边第一个蜡烛的位置
 * 2.右边端点的左边第一个蜡烛的位置
 * 3.这两个蜡烛之间有多少盘子
 * 0 1 2 3 4 5 6 7 8 9   下标
 * * * | * * | * * * |   字符串
 * <p>
 * - - 2 2 2 5 5 5 5 9   arrL
 * 2 2 2 5 5 5 9 9 9 9   arrR
 * 0 1 2 2 3 4 4 5 6 7   sum
 * 统计每个点左边最近和右边最近的蜡烛是一类简单的动态规划。
 * 而求两点之间某个类型的数量，是标准的前缀和应用
 */
public class TestDemo {

    public static int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length();
        //记录左边端点的右边第一个蜡烛的位置
        int[] left = new int[n];
        //记录右边端点的左边第一跟蜡烛的位置
        int[] right = new int[n];
        //记录第i个位置上前i-1个位置的蜡烛之和
        int[] sum = new int[n];

        char[] chars = s.toCharArray();
        for (int i = 0; i < n - 1; i++) {
            if (chars[i] == '*') {
                sum[i + 1] = sum[i] + 1;
            } else {
                sum[i + 1] = sum[i];
            }
        }
        int r = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            if (chars[i] == '|') {
                r = i;
                right[i] = r;
            } else {
                right[i] = r;
            }
        }
        int l = 0;
        for (int i = 0; i < n; i++) {
            if (chars[i] == '|') {
                l = i;
                left[i] = l;
            } else {
                left[i] = l;
            }
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            if (left[queries[i][1]] - 1 > right[queries[i][0]]) {
                ans[i] = sum[left[queries[i][1]]] - sum[right[queries[i][0]]];
            }
        }
        return ans;
    }

    public static void main1(String[] args) {
        String s = "**|**|***|";
        int[][] queries = {{2, 5}, {5, 9}};
        System.out.println(Arrays.toString(platesBetweenCandles(s, queries)));
    }
    //参数解析

    /**
     * 解析规则：
     * 1.参数分隔符为空格
     * 2.对于用""包含起来的参数，如果中间有空格，
     * 不能解析为多个参数。比如在命令行输入xcopy /s "C:\\program files" "d:\"时，
     * 参数仍然是4个，第3个参数应该是字符串C:\\program files，而不是C:\\program，
     * 注意输出参数时，需要将""去掉，引号不存在嵌套情况。
     * 3.参数不定长
     */
    //思路 识别是否有"";如果有就把""里的空格换成& 然后再按空格进行分割;分割完后再将&换成空格
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        StringBuilder tmp = new StringBuilder();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '"') {
                i += 1;
                while (s.charAt(i) != '"') {
                    if (s.charAt(i) != ' ') {
                        tmp.append(s.charAt(i));
                    } else {
                        tmp.append('&');
                    }
                    i++;
                }
            } else {
                tmp.append(s.charAt(i));
            }
        }
        String s1 = tmp.toString();
        String[] ans = s1.split(" ");
        System.out.println(ans.length);
        for (String a : ans) {
            if (a.contains("&")) {
                a = a.replaceAll("&", " ");
            }
            System.out.println(a);
        }
    }
    //跳石板
    /**链接：https://www.nowcoder.com/questionTerminal/4284c8f466814870bae7799a07d49ec8
     来源：牛客网

     小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3.......
     这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。
     例如：
     N = 4，M = 24：
     4->6->8->12->18->24
     于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板*/
    static int least = Integer.MAX_VALUE;
    public static void main3(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int sum = 0;
            leastJumpTime(0, n, m);
            System.out.println(least);
            least = Integer.MAX_VALUE;
        }
    }
    //递归 会超时
    private static void leastJumpTime(int sum, int n, int m) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                list.add(i);
            }
        }

        for (Integer a : list) {
            if (n + a == m) {
                sum++;
                least = Math.min(least, sum);

                return;
            } else if (n + a > m) {
                return;
            } else {

                leastJumpTime(sum + 1, n + a, m);
            }
        }
    }
    //动态dp
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        //数组长度为m;因为从n到m最多m步;
        int[] step = new int[m + 1];
        for (int i = 0; i < m + 1; i++) {
            step[i] = Integer.MAX_VALUE;
        }
        //从第几个阶梯起跳;则第几个阶梯为0步
        step[n] = 0;
        for (int i = n; i < m; i++) {
            if (step[i] == Integer.MAX_VALUE) {
                continue;
            }
            List<Integer> list = geiAppNums(i);
            for (int j : list) {
                if (i + j <= m && step[i + j] != Integer.MAX_VALUE) {
                    step[i + j] = Math.min(step[i + j], step[i] + 1);
                } else if (i + j <= m) {
                    step[i + j] = step[i] + 1;
                }
            }
        }
        if (step[m] == Integer.MAX_VALUE) {
            System.out.println("-1");
        } else {
            System.out.println(step[m]);
        }
    }
    //求约数
    private static List<Integer> geiAppNums(int head) {
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i <= Math.sqrt(head); i++) {
            if (head % i == 0) {
                list.add(i);
                if (head / i != i) {
                    list.add(head / i);
                }
            }
        }
        return list;
    }
}
